The present invention relates generally to a device and method for facilitating virtual connections between two different types of networks, each of which uses a different packet delivery scheme.
As is generally known, Ethernet and Internet Protocol (IP) are systems for transmitting packets between different points on a communications network. These switching systems are known as “contention-based” systems. That is, all transmitters contend for network resources. All transmitters may transmit simultaneously. If they do, then network resources may be oversubscribed. When this happens, data may be delayed or lost, resulting in network impairment.
As illustrated in FIG. 1, four streams of packets are input to a packet switch 112, which routes the packets to one or more outputs based on addressing information contained in each packet. Packets may arrive at the switch at unpredictable times, leading to bursts of inputs that must be handled. The switch typically maintains a packet queue 114 that is able to store a small number of packets. (In some devices, one queue is provided for each output port, such that if there are 8 ports, there may be 8 queues provided). Each queue may comprise multiple queues arranged by packet priority level, such that priority 3 packets, for example, take precedence over priority 1 packets. If the inputs are too bursty, the queues fill up and some packets may be discarded. The higher-priority queues are typically emptied before the lower-priority queues, such that the lower-priority queues are more likely to lose data first.
IP systems suffer from impairments such as packet loss and jitter. This happens because there is no control over how many such packets reach a router at any given instant. If two packets arrive at a router at the same time, destined for the same port, one will have to be delayed. Both cannot be transmitted simultaneously. One of the packets will be saved in the queue until the first packet is completely transmitted.
FIG. 2 shows a computer network comprising endpoints 100, 101, 102, and 103. The network includes routers 104 through 107. As shown in the figure, if endpoints 100 and 101 communicate with endpoints 102 and 103 at the same time, a bottleneck may develop between routers 105 and 106. This may occur because too many packets may be simultaneously transmitted between the routers, causing the routers to discard overflow packets. This can happen even at low levels of average network utilization.
Various methods have been developed to overcome data loss on Ethernet and IP networks. The primary approach has been to use additional protocols to replace lost data. This is an after-the-fact solution. An example is the well-known Transmission Control Protocol (TCP). TCP is able to detect data loss and it causes retransmission of the data, until a perfect copy of the complete data file is delivered to the recipient device.
One approach for providing reliable first-time delivery is to empirically determine the optimal scheduling of packets in the network by first transmitting test packets during different time periods and, after evaluating latency and/or dropped packet rates for each time period, selecting one or more time periods having favorable transmission characteristics. Packets that are dropped or delayed due to overloaded router queues will indicate unfavorable scheduling conditions, and the transmitting node can select a more favorable schedule for transmitting future packets to minimize the likelihood of packet loss. This approach is described in the previously-filed U.S. patent application Ser. No. 10/663,378 (filed on Aug. 17, 2003), which is described in detail below in conjunction with the principles of the present invention (see the heading entitled Empirical Scheduling of Network Packets below). Using this approach, a virtual connection can be established between two nodes in the network, such as a WAN comprising routers.
Another type of packet congestion problem may occur in a local area network (LAN) comprising LAN switches. As shown in FIG. 3, for example, a conventional network comprises a plurality of Local Area Network (LAN) endpoints, such as computers connected to an Ethernet LAN. The endpoints are coupled to one or more LAN switches 302, which connect through another part of the network to one or more additional LAN endpoints 303. When endpoint 301 sends packets to endpoint 303, the packets are sent through LAN switch 302, which also handles packets from other LAN endpoints. If too many packets are simultaneously transmitted by the other endpoints to 303, LAN switch 302 may have a queue overflow, causing packets to be lost. (The word “packets” will be used to refer to datagrams in a LAN or Wide Area Network (WAN) environment. In a LAN environment, packets are sometimes called “frames.” In a packet-switched WAN environment, packet-switching devices are normally referred to as “routers.”).
FIG. 4 illustrates the nature of the problem of dropped packets in the network of FIG. 3, which can occur in a LAN environment as well as a WAN environment. During periods where multiple endpoints are simultaneously transmitting packets on the network, the LAN switch 302 may become overloaded, such that some packets are discarded. This is typically caused by an internal queue in the LAN switch becoming full and thus becoming unable to accept new packets until the outgoing packets have been removed from the queue. This creates a problem in that transmitting endpoints cannot be guaranteed that their packets will arrive, necessitating other solutions such as the use of guaranteed-delivery protocols such as Transmission Control Protocol (TCP). Such solutions may be inappropriate for streaming video or other real-time applications, which cannot wait for retransmission of packets.
Another approach for providing reliable first-time delivery in a network of the type shown in FIG. 3 is to have the transmitting node and receiving node in a network agree on a transmission schedule that is compatible with both nodes. For example, when a transmitting node needs to establish a virtual connection with another node in the network, the transmitting node can send a proposed schedule to the receiving node indicating time interval locations during which it proposes to transmit future packets. The receiving node can compare this proposed “transmission map” with other scheduled deliveries at the receiving node and either accept the proposed transmission schedule or propose a different transmission schedule that will minimize packet congestion in the network. This approach is described in U.S. patent application Ser. No. 10/697,103, filed on Oct. 31, 2003, and described below in conjunction with the principles of the invention (see the heading entitled Negotiated Packet Delivery). Using this approach, a virtual connection can be established between two nodes in the network, such as a LAN comprising LAN switches.
It may be necessary to establish virtual connections between different types of networks having incompatible packet scheduling algorithms. For example, as shown in FIG. 5, a first endpoint 501 may be associated with a LAN 504 that employs the negotiated packet scheduling technique discussed above (i.e., endpoints in LAN 504 negotiate “transmission maps” in order to avoid congestion on network 504). A second endpoint 502 may be located on another LAN 508 that must be accessed through WAN 503 that employs the empirical packet scheduling technique discussed above (i.e., endpoints in WAN 503 transmit test packets to each other in order to empirically determine the most advantageous time periods for transmitting packets). If endpoint 501 needs to transmit packets to endpoint 502, difficulties may arise due to incompatible protocols being used for transmitting packets on the networks.